% TODO translate
\subsection{Простое шифрование используя XOR-маску, второй случай}
\label{XOR_mask_2}

Нашел еще один зашифрованный файл, который явно зашифрован чем-то простым вроде XOR-шифрования:

\begin{figure}[H]
\centering
\myincludegraphics{ff/XOR/mask_2/cipher.png}
\caption{Зашифрованный файл в Midnight Commander}
\end{figure}

Зашифрованный файл можно скачать \href{https://github.com/dennis714/RE-for-beginners/blob/master/ff/XOR/mask_2/files/cipher.txt}{здесь}.

Утилита \IT{ent} в Linux сообщает о $\textasciitilde{}7.5$ бит на байт, и это высокий уровень энтропии (\myref{entropy}),
что близко к сжатому или правильно зашифрованному файлу.
Но все-таки, мы ясно видим некоторый шаблон, здесь есть блоки длиной в 17 байт, и вы можете увидеть что-то вроде лестницы,
сдвигающеся на 1 байт на каждой 16-байтной линии.

Также известно, что исходный текст это текст на английском языке.

Предположим что этот фрагмент текста зашифрован простым XOR-шифрованием с 17-байтным ключом.

Я попробовал поискать повторяющиеся 17-байтные блоки при помощи Mathematica, как я делал это в моем предыдущем примере
(\myref{XOR_mask_1}):

\begin{lstlisting}[caption=Mathematica,style=custommath]
In[]:=input = BinaryReadList["/home/dennis/tmp/cipher.txt"];

In[]:=blocks = Partition[input, 17];

In[]:=Sort[Tally[blocks], #1[[2]] > #2[[2]] &]

Out[]:={{{248,128,88,63,58,175,159,154,232,226,161,50,97,127,3,217,80},1},
{{226,207,67,60,42,226,219,150,246,163,166,56,97,101,18,144,82},1},
{{228,128,79,49,59,250,137,154,165,236,169,118,53,122,31,217,65},1},
{{252,217,1,39,39,238,143,223,241,235,170,91,75,119,2,152,82},1},
{{244,204,88,112,59,234,151,147,165,238,170,118,49,126,27,144,95},1},
{{241,196,78,112,54,224,142,223,242,236,186,58,37,50,17,144,95},1},
{{176,201,71,112,56,230,143,151,234,246,187,118,44,125,8,156,17},1},
...
{{255,206,82,112,56,231,158,145,165,235,170,118,54,115,9,217,68},1},
{{249,206,71,34,42,254,142,154,235,247,239,57,34,113,27,138,88},1},
{{157,170,84,32,32,225,219,139,237,236,188,51,97,124,21,141,17},1},
{{248,197,1,61,32,253,149,150,235,228,188,122,97,97,27,143,84},1},
{{252,217,1,38,42,253,130,223,233,226,187,51,97,123,20,217,69},1},
{{245,211,13,112,56,231,148,223,242,226,188,118,52,97,15,152,93},1},
{{221,210,15,112,28,231,158,141,233,236,172,61,97,90,21,149,92},1}}
\end{lstlisting}

Ничего не выходит, каждый 17-байтный блок уникален внутри файла и встречается только один раз.
Возможно, здесь нет 17-байтных нулевых лакун (или лакун содержащих пробелы).
Это действительно возможно: подобное выравнивание пробелами может и отсутствовать в плотно сверстаном тексте.

Первая идея это попробовать все возможные 17-байтные ключи и найти тот, который после дешифровки приведет к читаемому тексту.
Полный перебор брутфорсом это не вариант, потому что здесь $256^{17}$ возможных ключей ($\textasciitilde{}10^{40}$),
это слишком.
Но есть и хорошие новости: кто сказал что нужно тестировать 17-байтный ключ как что-то целое, почему мы не можем тестировать
каждый байт ключа отдельно?
Это действительно возможно.

И алгоритм такой:

\begin{itemize}
\item попробовать все 256 байт для первого байта ключа;
\item дешифровать первый байт каждого 17-байтного блока в файле;
\item все ли полученные дешифрованные байты печатаемы? вести учет;
\item делать это для всех 17 байт ключа.
\end{itemize}

Я написал такой скрипт на Питоне для проверки этой идеи:

\begin{lstlisting}[caption=Python script,style=custompy]
each_Nth_byte=[""]*KEY_LEN

content=read_file(sys.argv[1])
# split input by 17-byte chunks:
all_chunks=chunks(content, KEY_LEN)
for c in all_chunks:
    for i in range(KEY_LEN):
        each_Nth_byte[i]=each_Nth_byte[i] + c[i]

# try each byte of key
for N in range(KEY_LEN):
    print "N=", N
    possible_keys=[]
    for i in range(256):
        tmp_key=chr(i)*len(each_Nth_byte[N])
        tmp=xor_strings(tmp_key,each_Nth_byte[N])
        # are all characters in tmp[] are printable?
        if is_string_printable(tmp)==False:
	    continue
	possible_keys.append(i)
    print possible_keys, "len=", len(possible_keys)
\end{lstlisting}

(Полная версия исходного кода \href{https://github.com/dennis714/RE-for-beginners/blob/master/ff/XOR/mask_2/files/decrypt2.py}{здесь}.)

И вот вывод:

\begin{lstlisting}
N= 0
[144, 145, 151] len= 3
N= 1
[160, 161] len= 2
N= 2
[32, 33, 38] len= 3
N= 3
[80, 81, 87] len= 3
N= 4
[78, 79] len= 2
N= 5
[142, 143] len= 2
N= 6
[250, 251] len= 2
N= 7
[254, 255] len= 2
N= 8
[130, 132, 133] len= 3
N= 9
[130, 131] len= 2
N= 10
[206, 207] len= 2
N= 11
[81, 86, 87] len= 3
N= 12
[64, 65] len= 2
N= 13
[18, 19] len= 2
N= 14
[122, 123] len= 2
N= 15
[248, 249] len= 2
N= 16
[48, 49] len= 2
\end{lstlisting}

Так что есть 2 или 3 возможных байта для каждого байта 17-байтного ключа.
Это намного лучше чем 256 возможных байт для каждого ключа, но все равно слишком.
Тут вплоть до одного миллиона возможных ключей:

\begin{lstlisting}[caption=Mathematica,style=custommath]
In[]:= 3*2*3*3*2*2*2*2*3*2*2*3*2*2*2*2*2
Out[]= 995328
\end{lstlisting}

Можно проверить их все, но затем нам придется проверять визуально, похож ли дешифрованный текст на текст на английском языке.

Также будет учитывать те факты, что мы имеем дело с 1) человеческим языком; 2) английским языком.
Человеческие языки имеют выдающиеся статистические особенности.
Прежде всего, пунктуация и длины слов.
Какая средняя длина слова в английском языке?
Просто будем считать пробелы в некоторых хорошо известных текстах на английском используя Mathematica.

Вот текст is \href{http://www.gutenberg.org/cache/epub/100/pg100.txt}{\q{The Complete Works of William Shakespeare}}
из библиотеки Гутенберга:

\begin{lstlisting}[caption=Mathematica,style=custommath]
In[]:= input = BinaryReadList["/home/dennis/tmp/pg100.txt"];

In[]:= Tally[input]
Out[]= {{239, 1}, {187, 1}, {191, 1}, {84, 39878}, {104, 
  218875}, {101, 406157}, {32, 1285884}, {80, 12038}, {114, 
  209907}, {111, 282560}, {106, 2788}, {99, 67194}, {116, 
  291243}, {71, 11261}, {117, 115225}, {110, 216805}, {98, 
  46768}, {103, 57328}, {69, 42703}, {66, 15450}, {107, 29345}, {102, 
  69103}, {67, 21526}, {109, 95890}, {112, 46849}, {108, 146532}, {87,
   16508}, {115, 215605}, {105, 199130}, {97, 245509}, {83, 
  34082}, {44, 83315}, {121, 85549}, {13, 124787}, {10, 124787}, {119,
   73155}, {100, 134216}, {118, 34077}, {46, 78216}, {89, 9128}, {45, 
  8150}, {76, 23919}, {42, 73}, {79, 33268}, {82, 29040}, {73, 
  55893}, {72, 18486}, {68, 15726}, {58, 1843}, {65, 44560}, {49, 
  982}, {50, 373}, {48, 325}, {91, 2076}, {35, 3}, {93, 2068}, {74, 
  2071}, {57, 966}, {52, 107}, {70, 11770}, {85, 14169}, {78, 
  27393}, {75, 6206}, {77, 15887}, {120, 4681}, {33, 8840}, {60, 
  468}, {86, 3587}, {51, 343}, {88, 608}, {40, 643}, {41, 644}, {62, 
  440}, {39, 31077}, {34, 488}, {59, 17199}, {126, 1}, {95, 71}, {113,
   2414}, {81, 1179}, {63, 10476}, {47, 48}, {55, 45}, {54, 73}, {64, 
  3}, {53, 94}, {56, 47}, {122, 1098}, {90, 532}, {124, 33}, {38, 
  21}, {96, 1}, {125, 2}, {37, 1}, {36, 2}}

In[]:= Length[input]/1285884 // N
Out[]= 4.34712
\end{lstlisting}

Тут 1285884 пробела во всем файле, и распространение пробелов это один пробел на $\textasciitilde{}4.3$ символов.

Теперь вот \href{http://www.gutenberg.org/ebooks/11}{Alice's Adventures in Wonderland, by Lewis Carroll} из той же библиотеки:

\begin{lstlisting}[caption=Mathematica,style=custommath]
In[]:= input = BinaryReadList["/home/dennis/tmp/pg11.txt"];

In[]:= Tally[input]
Out[]= {{239, 1}, {187, 1}, {191, 1}, {80, 172}, {114, 6398}, {111, 
  9243}, {106, 222}, {101, 15082}, {99, 2815}, {116, 11629}, {32, 
  27964}, {71, 193}, {117, 3867}, {110, 7869}, {98, 1621}, {103, 
  2750}, {39, 2885}, {115, 6980}, {65, 721}, {108, 5053}, {105, 
  7802}, {100, 5227}, {118, 911}, {87, 256}, {97, 9081}, {44, 
  2566}, {121, 2442}, {76, 158}, {119, 2696}, {67, 185}, {13, 
  3735}, {10, 3735}, {84, 571}, {104, 7580}, {66, 125}, {107, 
  1202}, {102, 2248}, {109, 2245}, {46, 1206}, {89, 142}, {112, 
  1796}, {45, 744}, {58, 255}, {68, 242}, {74, 13}, {50, 12}, {53, 
  13}, {48, 22}, {56, 10}, {91, 4}, {69, 313}, {35, 1}, {49, 68}, {93,
   4}, {82, 212}, {77, 222}, {57, 11}, {52, 10}, {42, 88}, {83, 
  288}, {79, 234}, {70, 134}, {72, 309}, {73, 831}, {85, 111}, {78, 
  182}, {75, 88}, {86, 52}, {51, 13}, {63, 202}, {40, 76}, {41, 
  76}, {59, 194}, {33, 451}, {113, 135}, {120, 170}, {90, 1}, {122, 
  79}, {34, 135}, {95, 4}, {81, 85}, {88, 6}, {47, 24}, {55, 6}, {54, 
  7}, {37, 1}, {64, 2}, {36, 2}}

In[]:= Length[input]/27964 // N
Out[]= 5.99049
\end{lstlisting}

Результат другой, вероятно потому что используется разное форматирование этих текстов (может быть из-за выравнивания
и отступов).

ОК, будем считать что средняя частота появления пробела в английском тексте это 1 пробел на 4..7 символов.

И снова хорошие новости: мы можем измерять частоту пробелов во время постепенного дешифрования файла.
Теперь я считаю пробелы в каждом \IT{ломтике} и выкидываю 1-байтные ключи, которые приводят к результатам со слишком
малым количеством пробелов
(или слишком большим, но это почти невозможно учитывая такой короткий ключ):

\begin{lstlisting}[caption=Python script,style=custompy]
each_Nth_byte=[""]*KEY_LEN

content=read_file(sys.argv[1])
# split input by 17-byte chunks:
all_chunks=chunks(content, KEY_LEN)
for c in all_chunks:
    for i in range(KEY_LEN):
        each_Nth_byte[i]=each_Nth_byte[i] + c[i]

# try each byte of key
for N in range(KEY_LEN):
    print "N=", N
    possible_keys=[]
    for i in range(256):
        tmp_key=chr(i)*len(each_Nth_byte[N])
        tmp=xor_strings(tmp_key,each_Nth_byte[N])
        # are all characters in tmp[] are printable?
        if is_string_printable(tmp)==False:
	    continue
        # count spaces in decrypted buffer:
	spaces=tmp.count(' ')
	if spaces==0:
            continue
	spaces_ratio=len(tmp)/spaces
	if spaces_ratio<4:
	    continue
	if spaces_ratio>7:
	    continue
	possible_keys.append(i)
    print possible_keys, "len=", len(possible_keys)
\end{lstlisting}

(Полная версия исходного кода \href{https://github.com/dennis714/RE-for-beginners/blob/master/ff/XOR/mask_2/files/decrypt3.py}{здесь}.)

Это выдает всего один возможный байт для каждого байта ключа:

\begin{lstlisting}
N= 0
[144] len= 1
N= 1
[160] len= 1
N= 2
[33] len= 1
N= 3
[80] len= 1
N= 4
[79] len= 1
N= 5
[143] len= 1
N= 6
[251] len= 1
N= 7
[255] len= 1
N= 8
[133] len= 1
N= 9
[131] len= 1
N= 10
[207] len= 1
N= 11
[86] len= 1
N= 12
[65] len= 1
N= 13
[18] len= 1
N= 14
[122] len= 1
N= 15
[249] len= 1
N= 16
[49] len= 1
\end{lstlisting}

Проверим этот ключ в Mathematica:

\begin{lstlisting}[caption=Mathematica,style=custommath]
In[]:= input = BinaryReadList["/home/dennis/tmp/cipher.txt"];

In[]:= blocks = Partition[input, 17];

In[]:= key = {144, 160, 33, 80, 79, 143, 251, 255, 133, 131, 207, 86, 65, 18, 122, 249, 49};

In[]:= EncryptBlock[blk_] := BitXor[key, blk]

In[]:= encrypted = Map[EncryptBlock[#] &, blocks];

In[]:= BinaryWrite["/home/dennis/tmp/plain2.txt", Flatten[encrypted]]

In[]:= Close["/home/dennis/tmp/plain2.txt"]
\end{lstlisting}

И дешифрованный текст:

\begin{lstlisting}
Mr. Sherlock Holmes, who was usually very late in the mornings, save
upon those not infrequent occasions when he was up all night, was seated
at the breakfast table. I stood upon the hearth-rug and picked up the
stick which our visitor had left behind him the night before. It was a
fine, thick piece of wood, bulbous-headed, of the sort which is known as
a "Penang lawyer." Just under the head was a broad silver band nearly
an inch across. "To James Mortimer, M.R.C.S., from his friends of the
C.C.H.," was engraved upon it, with the date "1884." It was just such a
stick as the old-fashioned family practitioner used to carry--dignified,
solid, and reassuring.

"Well, Watson, what do you make of it?"

Holmes was sitting with his back to me, and I had given him no sign of
my occupation.

...
\end{lstlisting}

(Полная версия текста \href{https://github.com/dennis714/RE-for-beginners/blob/master/ff/XOR/mask_2/files/plain.txt}{здесь}.)

Текст выглядит правильным.
Да, я придумал этот пример и выбрал хорошо известный текст Конан Дойля, но это очень близко к тому,
что у меня недавно было на практике.

\subsubsection{Другие идеи}

Если бы не получилось с подсчетом пробелов, вот еще идеи, которые можно было бы попробовать:

\begin{itemize}

\item Учитывать тот факт что буквы в нижнем регистре встречаются намного чаще, чем в верхнем.

\item Частотный анализ.

\item Есть очень хорошая техника для определения языка текста: триграммы.
Каждый язык имеет часто встречающиеся тройки буквы, для английского это могут быть \q{the} и \q{tha}.
Больше об этом:
\href{http://odur.let.rug.nl/~vannoord/TextCat/textcat.pdf}{N-Gram-Based Text Categorization},
\url{http://code.activestate.com/recipes/326576/}.
Интересно знать, что выявление триграмм может быть использовано при постепенном дешифровании текста, как в этом примере
(нужно просто проверять 3 рядом стоящих дешифрованных символа).

Для систем письменности отличных от латинского алфавита, закодированных в UTF-8, все может быть еще проще.
Например, в тексте на русском, закодированном в UTF-8, каждый байт перемежается с байтом 0xD0 или 0xD1.
Это потому что символы кириллицы расположен в 4-м блоке в таблице Уникода.
Другие системы письменности имеют свои блоки.

\end{itemize}

